// #include <stdio.h>
// #include <stdlib.h>
// #include <limits.h>
// #include"windows.h"
//
// #define MaxVertexNum 100 // 最大顶点数
// #define INF INT_MAX      // 无穷大
//
// typedef char VertexType; // 顶点数据类型
// typedef int EdgeType;    // 权值数据类型
//
// // 图的邻接矩阵存储结构
// typedef struct {
//     VertexType Ver[MaxVertexNum];          // 顶点表
//     EdgeType Edge[MaxVertexNum][MaxVertexNum]; // 邻接矩阵
//     int vexnum, arcnum;                    // 顶点数和边数
// } MGraph;
//
// // 初始化邻接矩阵图
// void InitMGraph(MGraph* G) {
//     G->vexnum = 0;
//     G->arcnum = 0;
//     for (int i = 0; i < MaxVertexNum; i++) {
//         for (int j = 0; j < MaxVertexNum; j++) {
//             if (i == j) {
//                 G->Edge[i][j] = 0; // 顶点到自身的距离为 0
//             } else {
//                 G->Edge[i][j] = INF; // 初始化为无穷大
//             }
//         }
//     }
// }
//
// // 添加顶点到邻接矩阵图
// void AddVertexM(MGraph* G, VertexType v) {
//     if (G->vexnum < MaxVertexNum) {
//         G->Ver[G->vexnum] = v;
//         G->vexnum++;
//     }
// }
//
// // 添加边到邻接矩阵图
// void AddEdgeM(MGraph* G, int v1, int v2, EdgeType weight) {
//     if (v1 >= 0 && v1 < G->vexnum && v2 >= 0 && v2 < G->vexnum) {
//         G->Edge[v1][v2] = weight;
//         // 如果是无向图，需要对称赋值
//         // G->Edge[v2][v1] = weight;
//         G->arcnum++;
//     }
// }
//
// // Floyd 算法求解单源最短路径
// void FloydShortestPath(MGraph* G, int start) {
//     if (start < 0 || start >= G->vexnum) {
//         printf("错误：起始顶点编号超出范围！\n");
//         return;
//     }
//
//     // 初始化距离矩阵和路径矩阵
//     EdgeType dist[MaxVertexNum][MaxVertexNum]; // 存储最短距离
//     int path[MaxVertexNum][MaxVertexNum];      // 存储路径信息
//
//     for (int i = 0; i < G->vexnum; i++) {
//         for (int j = 0; j < G->vexnum; j++) {
//             dist[i][j] = G->Edge[i][j]; // 初始化为邻接矩阵的值
//             if (i != j && G->Edge[i][j] != INF) {
//                 path[i][j] = i; // 如果 i 和 j 之间有边，则 j 的前驱是 i
//             } else {
//                 path[i][j] = -1; // 否则前驱为 -1
//             }
//         }
//     }
//
//     // Floyd 算法核心部分
//     for (int k = 0; k < G->vexnum; k++) {
//         for (int i = 0; i < G->vexnum; i++) {
//             for (int j = 0; j < G->vexnum; j++) {
//                 if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) {
//                     dist[i][j] = dist[i][k] + dist[k][j]; // 更新最短距离
//                     path[i][j] = path[k][j]; // 更新路径信息
//                 }
//             }
//         }
//     }
//
//     // 输出从起始顶点到其他顶点的最短路径和距离
//     printf("从顶点 %c 到其他顶点的最短路径和距离：\n", G->Ver[start]);
//     for (int i = 0; i < G->vexnum; i++) {
//         if (i == start) continue; // 跳过起始顶点
//
//         if (dist[start][i] == INF) {
//             printf("到顶点 %c 的最短距离: 不可达\n", G->Ver[i]);
//         } else {
//             printf("到顶点 %c 的最短距离: %d，路径: ", G->Ver[i], dist[start][i]);
//
//             // 输出路径
//             int current = i;
//             int stack[MaxVertexNum], top = -1; // 使用栈逆序输出路径
//             while (current != start) {
//                 stack[++top] = current;
//                 current = path[start][current];
//             }
//             stack[++top] = start;
//
//             while (top >= 0) {
//                 printf("%c", G->Ver[stack[top--]]);
//                 if (top >= 0) printf(" -> ");
//             }
//             printf("\n");
//         }
//     }
// }
//
// int main() {
//     SetConsoleOutputCP(CP_UTF8);
//     MGraph G;
//     InitMGraph(&G);
//
//     // 添加顶点
//     AddVertexM(&G, 'A');
//     AddVertexM(&G, 'B');
//     AddVertexM(&G, 'C');
//     AddVertexM(&G, 'D');
//     AddVertexM(&G, 'E');
//
//     // 添加边
//     AddEdgeM(&G, 0, 1, 2); // A -> B, 权重 2
//     AddEdgeM(&G, 0, 2, 4); // A -> C, 权重 4
//     AddEdgeM(&G, 1, 2, 1); // B -> C, 权重 1
//     AddEdgeM(&G, 1, 3, 7); // B -> D, 权重 7
//     AddEdgeM(&G, 2, 4, 3); // C -> E, 权重 3
//     AddEdgeM(&G, 3, 4, 1); // D -> E, 权重 1
//
//     // 执行 Floyd 单源最短路径
//     FloydShortestPath(&G, 0); // 从顶点 A 开始
//
//     return 0;
// }